package top.minuy.structure.graph.cc.bfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 联通分量，广度优先遍历
 *
 * @author Minuy
 * @time 10:25
 * @date 2021/11/20
 */
public class CC {

    private Graph g;
    private boolean[] isVisited;
    private int CCount;
    private int[] CCId;

    public CC(Graph g) {
        this.g = g;

        if (g.isDirected()){
            throw new IllegalArgumentException("CC only works in undirected graph.");
        }

        isVisited = new boolean[g.V()];
        CCId = new int[g.V()];
        for (int i = 0; i < CCId.length; i++) {
            CCId[i] = -1;
        }

        CCount = 0;

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                bfs(v, CCount);
                // System.out.println("根顶点："+v);
                CCount++;
            }
        }
    }

    private void bfs(int v, int CCId) {
        List<Integer> queue = new ArrayList<>();
        queue.add(v); // 根顶点入队
        isVisited[v] = true; // 入队的时候设置为true
        // System.out.println("根顶点入队："+v);
        // System.out.println("==============");
        while (!queue.isEmpty()) {
            // 第一个元素出队
            v = queue.remove(0);
            // System.out.println("第一个元素出队并访问："+v);

            // 访问
            // order.add(v);
            this.CCId[v] = CCId;

            for (int w : g.adj(v)) {
                if (!isVisited[w]) {  // 如果没被访问过
                    queue.add(w);  // 入队
                    // System.out.println("子顶点入队："+w);
                    isVisited[w] = true; // 入队的时候设置为true
                }
            }
        }
    }

    /**
     * 获取联通分量
     *
     * @return int 联通分量
     * @author Minuy
     * @date 2021/11/20 10:28
     */
    public int count() {
        return CCount;
    }

    /**
     * 判断两个顶点是否相连
     *
     * @param s 顶点1
     * @param t 顶点2
     * @return boolean 两顶点是否相连
     * @author Minuy
     * @date 2021/11/20 10:37
     */
    public boolean isConnected(int s, int t) {
        g.validateVertex(s);
        g.validateVertex(t);
        return CCId[s] == CCId[t];
    }

    /**
     * 获取所有联通分量的成员
     *
     * @return ArrayList<Integer> 所有联通分量的成员
     * @author Minuy
     * @date 2021/11/20 10:37
     */
    public ArrayList<Integer>[] components() {
        ArrayList<Integer>[] ret = new ArrayList[CCount];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = new ArrayList<Integer>();
        }

        for (int v = 0; v < CCId.length; v++) {
            ret[CCId[v]].add(v);
        }

        return ret;
    }
}
